from typing import *


# Definition for singly-linked list.
class ListNode:

    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:

    def detectCycle(self, head: ListNode) -> ListNode:
        s, f = head, head
        while s is not None and f is not None:
            s = s.next
            f = f.next
            if f is not None:
                f = f.next
            if s == f:
                break
        if s is None or f is None:
            return None
        p = head
        while p != s:
            p = p.next
            s = s.next
        return p


def array_list_node(arr: List[int]):
    pass


if __name__ == '__main__':
    arr = [3, 2, 0, -4]
    list: List[ListNode] = [ListNode(x) for x in arr]
    next = [1, 2, 3, 1]
    for i, n in enumerate(next):
        list[i].next = list[n]
    s = Solution()
    print(s.detectCycle(list[0]).val)